package com.practice.niuke.new_direct_practice.class16;

/**
 * 给定一颗二叉树的头节点head，任意a、b亮点之间都有路径，就是a一路不重复走过任何
 * 一个点，最后到达b这条路。这条路的路径和就是沿途数字累加起来（包括a、b）。求二
 * 叉树上最大的路径累加和。
 */
public class Code03_BinaryTreeMaximumPathSum {

	/**
	 * 二叉树的节点
	 */
	public class Node {
		int value;
		public Node left;
		public Node right;
	}

	/**
	 * 二叉树的递归套路的统一信息整合（统一返回体）
	 */
	public static class Info{
		// 最大路径和
		public int maxPathSum;
		// 必须从头节点出发的最大路径和
		public int fromHeadMaxPathSum;

		public Info(int maxPathSum, int fromHeadMaxPathSum) {
			this.maxPathSum = maxPathSum;
			this.fromHeadMaxPathSum = fromHeadMaxPathSum;
		}
	}

	/**
	 * 二叉树的递归套路（递归函数）
	 *
	 * @param x 从x节点出发时的情况
	 * @return Info
	 */
	public static Info process(Node x){
		if (x == null){
			return null;
		}
		// 左树上的信息
		Info leftInfo = process(x.left);
		// 右树上的信息
		Info rightInfo = process(x.right);
		int maxPathSum;
		int fromHeadMaxPathSum;
		// 可能性1
		int p1 = Integer.MIN_VALUE;
		if (leftInfo != null){
			p1 = leftInfo.maxPathSum;
		}
		int p2 = Integer.MIN_VALUE;
		if (rightInfo != null){
			p2 = rightInfo.maxPathSum;
		}
		int p3 = x.value;
		int p4 = Integer.MIN_VALUE;
		if (leftInfo != null){
			p4 = x.value + leftInfo.fromHeadMaxPathSum;
		}
		int p5 = Integer.MIN_VALUE;
		if (rightInfo != null){
			p5 = x.value + rightInfo.fromHeadMaxPathSum;
		}
		int p6 = Integer.MIN_VALUE;
		if (leftInfo != null && rightInfo != null){
			p6 =x.value + leftInfo.fromHeadMaxPathSum + rightInfo.fromHeadMaxPathSum;
		}
		maxPathSum = Math.max(Math.max(Math.max(Math.max(Math.max(p1, p2), p3), p4), p5), p6);
		fromHeadMaxPathSum = Math.max(Math.max(p4, p3), p5);
		return new Info(maxPathSum, fromHeadMaxPathSum);
	}

	/**
	 * 二叉树的递归套路，主函数（TODO：标记主函数，调用了递归函数process）
	 *
	 * @param head 二叉树的头节点
	 * @return int
	 */
	public static int mainProcess(Node head){
		return process(head).maxPathSum;
	}

}
